package edu.rice;

import java.util.Random;

public class Sort {

	//mine
	static void insertsort1(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int key = a[i];
			for (int j = i - 1; j >= 0; j--) {
				if (key < a[j]) {
					int tmp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = tmp;
				} else {
					break;
				}
			}
		}
	}

	//From book
	static void insertsort(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int key = a[i];
			int j = i - 1;
			while (j >= 0 && a[j] > key) {
				a[j + 1] = a[j];
				j = j - 1;
			}
			a[j + 1] = key;
		}
	}
	
	static int[] add(int[] a, int[] b){
		int[] ans = new int[a.length +1];
		int c = 0;
		for(int i = 0; i < a.length; i++){
			ans[i] = a[i] + b[i] + c;
			c = ans[i]/10;
			ans[i] %= 10;
		}
		ans[a.length] = c;
		return ans;
	}

	public static void main(String[] args) {
		Random r = new Random();
		r.setSeed(10000000);
		int N = 20;
		int[] a = new int[N];
		int[] b = new int[N];
		for (int i = 0; i < N; i++) {
			a[i] = r.nextInt(10);
			b[i] = r.nextInt(10);
		}
		print(a);
		System.out.println();
		print(b);
		System.out.println();
//		insertsort1(a);
		int[] c = add(a,b);
		System.out.println("After insert sort:");
//		print(a);
		print(c);
	}

	static void print(int[] a) {
		int N = a.length;
		if (a.length > 100) {
			System.out
					.println("Array size is too large. Only print first 100 item");
			N = 100;

		}
		for (int i = 0; i < N; i++) {
			System.out.print(a[i]);
			if ((i + 1) % 50 == 0) {
				System.out.println();
			} else {
				System.out.print(", ");
			}
		}
	}
}
